class Solution
{
public:
    int minimumCost(string target, vector<string> &words, vector<int> &costs)
    {
        int minimumCost(string target, vector<string> & words, vector<int> & costs)
        {
            int n = target.size();
            vector<unordered_map<int, int>> graph(n + 1);

            unordered_map<string, int> wordCosts;
            for (int i = 0; i < words.size(); ++i)
            {
                if (wordCosts.count(words[i]))
                {
                    wordCosts[words[i]] = min(wordCosts[words[i]], costs[i]);
                }
                else
                {
                    wordCosts[words[i]] = costs[i];
                }
            }

            auto findAll = [&](const string &s, int cost)
            {
                int m = s.size();
                vector<int> next(m, -1);
                for (int i = 1, j = -1; i < m; ++i)
                {
                    while (j != -1 && s[i] != s[j + 1])
                    {
                        j = next[j];
                    }
                    if (s[i] == s[j + 1])
                    {
                        ++j;
                    }
                    next[i] = j;
                }
                for (int i = 0, j = -1; i < n; ++i)
                {
                    while (j != -1 && target[i] != s[j + 1])
                    {
                        j = next[j];
                    }
                    if (target[i] == s[j + 1])
                    {
                        ++j;
                    }
                    if (j == m - 1)
                    {
                        int index = i - m + 1;
                        if (graph[index].count(index + m))
                        {
                            graph[index][index + m] = min(graph[index][index + m], cost);
                        }
                        else
                        {
                            graph[index][index + m] = cost;
                        }

                        j = next[j];
                    }
                }
            };

            for (auto &[word, cost] : wordCosts)
            {
                findAll(word, cost);
            }

            vector<int> dist(n + 1, INT_MAX);
            dist[0] = 0;
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            pq.push({0, 0});
            while (!pq.empty())
            {
                auto [d, u] = pq.top();
                pq.pop();
                if (d > dist[u])
                {
                    continue;
                }
                for (auto &[v, w] : graph[u])
                {
                    if (dist[u] + w < dist[v])
                    {
                        dist[v] = dist[u] + w;
                        pq.push({dist[v], v});
                    }
                }
            }

            return dist[n] == INT_MAX ? -1 : dist[n];
        }

        int minimumCost(string target, vector<string> & words, vector<int> & costs)
        {
            unordered_map<string_view, int> wordCosts;
            unordered_set<int> wordLengths;
            for (int i = 0; i < words.size(); ++i)
            {
                if (wordCosts.count(words[i]))
                {
                    wordCosts[words[i]] = min(wordCosts[words[i]], costs[i]);
                }
                else
                {
                    wordCosts[words[i]] = costs[i];
                }
                wordLengths.insert(words[i].size());
            }

            string_view targetView = target;
            vector<int> mem(target.size(), -2);

            function<int(int)> f = [&](int pos)
            {
                if (pos == target.size())
                {
                    return 0;
                }
                if (mem[pos] != -2)
                {
                    return mem[pos];
                }
                int res = -1;
                for (int len : wordLengths)
                {
                    if (pos + len <= target.size())
                    {
                        string_view sv = targetView.substr(pos, len);
                        if (!wordCosts.count(sv))
                        {
                            continue;
                        }
                        int nextCost = f(pos + len);
                        if (nextCost == -1)
                        {
                            continue;
                        }
                        if (res == -1)
                        {
                            res = nextCost + wordCosts[sv];
                        }
                        else
                        {
                            res = min(res, nextCost + wordCosts[sv]);
                        }
                    }
                }
                mem[pos] = res;
                return res;
            };

            return f(0);
        }
    }
};